package com.cat.dataStructure03;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/?envType=daily-question&envId=2025-11-12
 * @create 2025/11/12 12:50
 * @since JDK17
 */

public class Solution46 {
    int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
    public int minOperations(int[] nums) {
        int g = 0, n = nums.length;
        for (int x : nums) {
            g = gcd(g, x);
        }
        if (g > 1) {
            return -1;
        }
        int one = 0;
        for (int x : nums) {
            one += x == 1 ? 1 : 0;
        }
        if (one != 0) {
            return n - one;
        }
        int ans = n;
        for (int i = 0; i < n; i++) {
            g = 0;
            for (int j = i; j < n; j++) {
                g = gcd(g, nums[j]);
                if (g == 1) {
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }

        return n + ans - 2;
    }
}
